|
The cover tree is a type of data structure in computer science that is specifically designed to facilitate the speed-up of a nearest neighbor search. It is a refinement of the Navigating Net data structure, and related to a variety of other data structures developed for indexing intrinsically low-dimensional data.〔Kenneth Clarkson. Nearest-neighbor searching and metric space dimensions. In G. Shakhnarovich, T. Darrell, and P. Indyk, editors, Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, pages 15--59. MIT Press, 2006.〕 The tree can be thought of as a hierarchy of levels with the top level containing the root point and the bottom level containing every point in the metric space. Each level ''C'' is associated with an integer value ''i'' that decrements by one as the tree is descended. Each level ''C'' in the cover tree has three important properties: *Nesting: *Covering: For every point , there exists a point such that the distance from to is less than or equal to and exactly one such is a parent of . *Separation: For all points , the distance from to is greater than . == Complexity == 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「cover tree」の詳細全文を読む スポンサード リンク
|